#include <vector>
#include <string>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
using namespace std;

// 两数之和
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hash;
        for (int i = 0; i < nums.size(); i++)
        {
            if (hash.count(target - nums[i])) return {hash[target-nums[i]], i};
            hash[nums[i]] = i;
        }
        return {-1, -1};
    }
};

// 判定是否互为字符重排
class Solution {
public:
    bool CheckPermutation(string s1, string s2) {
        if (s1.size() != s2.size()) return false;
        int hash[26] = {0};
        for (auto ch : s1) hash[ch - 'a']++;
        for (auto ch : s2)
        {
            if (hash[ch - 'a']) hash[ch - 'a']--;
            else return false;
        }
        return true;
    }
};

// 存在重复元素I
class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> hash;
        for (int e : nums)
        {
            if (hash.count(e)) return true;
            else hash.insert(e);
        }
        return false;
    }
};

// 存在重复元素II
class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        unordered_map<int, int> hash; //<nums[i], i>
        for (int i = 0; i < nums.size(); i++)
        {
            if (hash.count(nums[i])) 
            {
                if (i - hash[nums[i]] <= k)
                    return true;
            }
            hash[nums[i]] = i;
        }
        return false;
    }
};

// 字母异位词分组
class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hash;
        for (auto &s : strs)
        {
            string tmp = s;
            sort(tmp.begin(), tmp.end());
            hash[tmp].push_back(s);
        }
        vector<vector<string>> ret;
        for (auto &e : hash)
        {
            ret.push_back(e.second);
        }
        return ret;
    }
};

// 最长连续序列
class Solution {
    public:
        int longestConsecutive(vector<int>& nums) {
            unordered_set<int> hash;
            for (auto e : nums) hash.insert(e); // 先将所有数字存起来
            int maxlen = 0;
            for (auto e : hash)
            {
                if (!hash.count(e - 1)) // 找到一段连续的左边界
                {
                    int len = 1;
                    while (hash.count(e + 1)) // 统计右边有多长
                    {
                        len++;
                        e++;
                    }
                    maxlen = max(maxlen, len); // 得出最长长度
                }
            }
            return maxlen;
        }
    };